// 输入: nums = [1,3,5,6], target = 4
// 输出: 2

function findPosi1 (nums, target) {
    for (let i = 0; i < nums.length; i++) {
        const num = nums[i];
        if (num >= target) {
            return i;
        }
    }
    return nums.length;
}

function findPosi2 (nums, target) {
    let totalLen = nums.length;

    if (target < nums[0]) {
        return 0;
    }
    if (target > nums[totalLen - 1]) {
        return totalLen;
    }

    let position = .5;
    let prevIndex = Math.floor(totalLen * position);
    let mid = nums[prevIndex];
    let count = 1; // 1 / 2
    while (mid !== target) {

        if (mid < target) {
            position += .5 ** ++count;
            
        }
        if (mid > target) {
            position -= .5 ** ++count;
        }

        const index = Math.floor(totalLen * position);

        if (index - prevIndex === 1 || index - prevIndex === -1) {
            return index > prevIndex ? index : prevIndex;
        }
        // if (Math.abs(index - prevIndex) === 1) {
        //     return Math.max(index, prevIndex);
        // }
        mid = nums[index];
        prevIndex = index;
    }
    return prevIndex;
}

function findPosi3 (nums, target) {
    let totalLen = nums.length;

    if (target < nums[0]) {
        return 0;
    }
    if (target > nums[totalLen - 1]) {
        return totalLen;
    }

    let left = 0;
    let right = totalLen - 1;
    let prevIndex = left;
    let prevMid = nums[left];
    while (prevMid !== target) {

        const index = Math.floor((left + right) / 2);

        if (index - prevIndex === 1 || index - prevIndex === -1) {
            return index > prevIndex ? index : prevIndex;
        }

        const mid = nums[index]

        if (target > mid) {
            left = index;
        }
        if (target < mid) {
            right = index;
        }
        
        prevMid = mid;
        prevIndex = index;
    }
    return prevIndex;
}

function findPosi4 (nums, target) {

    let totalLen = nums.length;

    if (target < nums[0]) {
        return 0;
    }

    if (target > nums[totalLen - 1]) {
        return totalLen;
    }

    let leftIndex = 0;
    let rightIndex = totalLen - 1;

    while (true) {
        const midIndex = Math.floor((leftIndex + rightIndex) / 2);
        const mid = nums[midIndex];
        if (target > mid) {
            leftIndex = midIndex;
        }
        if (target < mid) {
            rightIndex = midIndex;
        }
        if (target === mid) {
            return midIndex;
        }
        if (Math.abs(leftIndex - rightIndex) === 1) {
            return rightIndex;
        }
    }

}

console.log(findPosi2([1,3,5,6], 0)); // 0
console.log(findPosi2([1,3,5,6], 7)); // 4
console.log(findPosi2([1,3,5,6], 5)); // 2
console.log(findPosi2([1,3,5,6], 4)); // 2

function performance (name, cb, count = 1000) {
    console.time(name);
    for (let i = 0; i < count; i++) {
        cb();
    }
    console.timeEnd(name);
}

const makeData = () => Array.from(new Set(new Array(500000).fill(0).map(() => Math.floor(Math.random() * 10000000)))).sort((a, b) => a - b);

const data = makeData();

performance('1', () => {
    findPosi1(data, 9000000);
});

performance('2', () => {
    findPosi2(data, 9000000);
});

performance('4', () => {
    findPosi4(data, 9000000);
});